import common.Node;

/**
 * 138. Copy List with Random Pointer 随机链表的复制
 * https://leetcode.com/problems/copy-list-with-random-pointer/description/
 */
class CopyListWithRandomPointer {
    /**
     * 方法：复制带随机指针的链表
     *      1. 在每个节点后复制一个新节点
     *      2. 设置新节点的random指针
     *      3. 分离原链表和复制的链表
     *
     * Args:
     *      head: Node - 链表头节点
     *
     * Returns:
     *      Node: 复制后的新链表头节点
     *
     * Time: O(n) - 需要遍历链表3次
     *
     * Space: O(1) - 只使用常数额外空间
     */
    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }
        // 复制每个节点，把新节点直接插到原节点的后面
        for (Node cur = head; cur != null; cur = cur.next.next){
            cur.next = new Node(cur.val, cur.next);
        }
        // 遍历交错链表中的原链表节点
        for (Node cur = head; cur != null; cur = cur.next.next){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
        }
        // 把交错链表分离成两个链表
        Node newHead = head.next;
        Node cur = head;
        for(; cur.next.next != null; cur = cur.next){
            Node copy = cur.next;
            cur.next = copy.next;
            copy.next = copy.next.next;
        }
        cur.next = null;
        return newHead;

    }
}